home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 185_01 / ssort.c < prev    next >
Text File  |  1985-08-19  |  22KB  |  880 lines
  1. /*
  2.  * SSORT.C - Selecta-SORT
  3.  * version 1.0
  4.  * This is a modified version of LEXSORT which permits a command line
  5.  * option to select the collating sequence from a "magic" file.
  6.  * The name was changed only due to the fact that LEXSORT was no longer
  7.  * (if it ever was) appropriate.  LEXSORT.LBR should be retired.
  8.  *
  9.  * Differences from LEXSORT.C:
  10.  *
  11.  * The only changed functions were options() and usage(). Two functions
  12.  * were added: get_collating_sequence(), collate_file().
  13.  * Four #defines were added:  INPUT, ABSOLUTE, FUDGE, COLLATE_NAME.
  14.  * The signon message was changed.  Globals were not modified.
  15.  *
  16.  *    Harvey Moran    2/26/84
  17.  *
  18.  * To build with BDS C vers 1.5:
  19.  *    cc ssort -o -e 3800
  20.  *    casm lexlate
  21.  *    asm lexlate.DDz        ;choose drives (D) to suit
  22.  *    ddt
  23.  *    f100,1000,0  (not necessary, makes file compares of '.crl' meaningful)
  24.  *    iLEXLATE.HEX
  25.  *    g0
  26.  *    save 4 lexlate.crl
  27.  *    l2 ssort lexlate
  28.  *
  29.  * Usage:
  30.  *
  31.  *    SSORT <infile> <outfile> [-c<index 0 to n>] [-k<key field selections>]
  32.  *
  33.  *    -c<n> seletcs the n'th sort order precedence table from the
  34.  *    "magic" file SSORT.OVL to be overlayed into lexlate().  See
  35.  *    SORTORDR.ASM for the definition of these tables. ASseMble and LOAD
  36.  *    SORTORDR.ASM, then rename to SSORT.OVL. 
  37.  *    If -c is not used, the default remains the same lexicographical
  38.  *    increasing order sort from LEXSORT (or whatever you "wire" into
  39.  *    LEXLATE.CRL).
  40.  *
  41.  *    All other command line syntax remains the same as LEXSORT.
  42.  *
  43.  *        Harvey Moran 2/26/84
  44.  *
  45.  * =====================================================================
  46.  * LEXSORT.C (modified SORT3.C for lexicographical ordering) HRM 11/6/83
  47.  * version 1.0
  48.  * To build with BDS C vers 1.5:
  49.  *    cc lexsort -o -e 3400
  50.  *    casm lexlate
  51.  *    asm lexlate.DDz        ;choose drives (D) to suit
  52.  *    ddt
  53.  *    f100,1000,0  (not necessary, makes file compares of '.crl' meaningful)
  54.  *    iLEXLATE.HEX
  55.  *    g0
  56.  *    save 4 lexlate.crl
  57.  *    l2 lexsort lexlate
  58.  *
  59.  * Usage: lexsort <infile> <outfile> [-k<sort key list>]
  60.  *
  61.  * where <sort key list> is:
  62.  *
  63.  * A comma separated list of column numbers or ranges
  64.  * specifing the sort key positions.
  65.  *    e.g.
  66.  * lexsort messy.dat neat.dat -k3-5,7-9,1-2,12
  67.  *
  68.  * specifies that:
  69.  * the  input file is MESSY.DAT
  70.  * the output file is  NEAT.DAT
  71.  *
  72.  *         The primary sort key is columns  3 thru 5
  73.  * The first secondary sort key is columns  7 thru 9
  74.  * The next  secondary sort key is columns  1 thru 2
  75.  * The last  secondary sort key is columns 12 thru end of line
  76.  *
  77.  * A sort key of 1 column may be specified as 3-3 for example.
  78.  * A sort key which goes to end of line need NOT be the last one.
  79.  *
  80.  * The leftmost column is numbered 1.
  81.  * The default sort key is the entire line.
  82.  *
  83.  * Implementation note:
  84.  *
  85.  *    LEXLATE.CSM contains function lexlate() which determines the
  86.  *    character ordering for the character set.  This concept includes
  87.  *    the notion of totally INGOREing some characters.  The LEXLATE.CSM
  88.  *    provided IGNOREs all characters but space, A-Z, a-z, 0-9.  It also
  89.  *    treats 'A' as less than but adjacent to 'a', etc.  If a specified
  90.  *    key field consists entirely of IGNORE characters, it is considered
  91.  *    the lowest order for that key.  A line which has no entry for the
  92.  *    specified key field (because it is too short) will be the next lowest
  93.  *    order in the sort for that field.
  94.  *
  95.  * Derived from: SORT3.C by H.R. Moran, Jr. 11/5/83
  96.  * changes made:
  97.  *    1) Re-format, indent, and comment to suit me, including deletion
  98.  *       of some extraneous declarations and code lines.
  99.  *    2) Re-write compar(), and include use of lexlate()
  100.  *    3) Add options() to allow key field selections.
  101.  *
  102.  * SORT3.C comments follow:
  103.  * --------------------------------------------------------------------------- 
  104.  *    Sort/Merge from Software Tools
  105.  *
  106.  *    Last Modified : 21 September 1982
  107.  *
  108.  *    Converted from Software Tools RATFOR to BDS C by Leor Zolman
  109.  *    Sep 2, 1982
  110.  *
  111.  *    Usage: sort <infile> <outfile>
  112.  *
  113.  *    Main variables have been made external; this is pretty much in
  114.  *    line with the RATFOR call-by-name convention anyway.
  115.  *
  116.  *    Requires lots of disk space, up to around three times the length
  117.  *    of the file file being sorted. This program is intended for files
  118.  *    bigger than memory; simpler, faster sorts can be implemented for
  119.  *    really short files (like ALPH.C)
  120.  *        -leor
  121.  *
  122.  *    Compile & Link:
  123.  *        A>cc sort.c -e2800 -o
  124.  *        A>l2 sort
  125.  *    (or...)
  126.  *        A>cc sort.c -e2900 -o
  127.  *        A>clink sort
  128.  *
  129.  */
  130.  
  131.  
  132. #include <bdscio.h>
  133.  
  134. #define SIGNON "ssort version 1.0 - 2/26/84 - hrm\n"
  135.  
  136. #define FUDGE 0xe /* offset into the lexlate function for table address */
  137. #define COLLATE_NAME collate_file()
  138.  
  139. /* #define DEBUG */    /* enables debug printout when defined */
  140.  
  141. #define BOOL  int        /* BOOlean */
  142. #define PROC  int        /* PROCedure */
  143. #define TRIAD int        /* -1, 0, or +1 */
  144.  
  145. #define IGNORE 0xff        /* lexlate() token to ignore the character */
  146.  
  147. #define VERBOSE 1        /* give running account of file activity */
  148.  
  149. #define MAXLINE 200        /* longest line we want to deal with */
  150. #define NBUFS 7            /* Max number of open buffered files */
  151. #define MAXPTR  3000        /* Max number of lines (set for dict) */
  152. #define MERGEORDER (NBUFS-1)    /* Max # of intermediate files to merge */
  153. #define NAMESIZE 20        /* Max Filename size */
  154. #define LOGPTR 13        /* smallest value >= log (base 2) of  MAXPTR */
  155. #define EOS '\0'        /* string termination character */
  156. #define FILE struct _buf
  157.  
  158. #define stderr 4
  159. #define fputc putc
  160.  
  161. char name[NAMESIZE], name2[NAMESIZE + 10];
  162. FILE buffers[NBUFS + 1];    /* up to NBUFS general-purp. buffered files */
  163. FILE *infil[MERGEORDER + 1];    /* tmp file ptrs for sort operation */
  164. unsigned linptr[MAXPTR + 1], nlines;
  165. int temp;
  166. unsigned maxtext;        /* max # of chars in main text buffer */
  167.  
  168. /*
  169.  * KEY FIELD selection support variables - hrm
  170.  */
  171. #define MAXFIELDS 20
  172. #define FIELDS struct _fields
  173.  
  174. FIELDS {
  175.   int _numfields;
  176.   int _strtcol[MAXFIELDS];
  177.   int _stopcol[MAXFIELDS];
  178.   } sortfields;
  179.  
  180. #define FASTLOCAL
  181.  
  182. #ifdef FASTLOCAL
  183.  
  184. /*
  185.  * FAST locals for compar()
  186.  */
  187. struct {
  188.   unsigned i, j;
  189.   unsigned k, l;
  190.   unsigned x1, x2;
  191.   unsigned len_i, len_j;
  192.   char c1, c2;
  193.   } z;
  194. #endif
  195.  
  196. #ifdef DEBUG
  197. char spacebuffer[200];
  198. #endif
  199.  
  200. /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
  201. /*!!!!!!!!!!!!!!!!              WARNING  (H.Moran)             !!!!!!!!! */
  202. /*! The algorithm INSISTS that THIS name be the LAST global           ! */
  203. /*!                                                                    ! */
  204. char *linbuf;        /* text area starts after this variable */
  205. /*                                                                       */
  206. /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
  207.  
  208. main(argc, argv)
  209.   int argc;
  210.   char *argv[];
  211. {
  212.  
  213.     int min(), gtext();
  214.  
  215.     FILE *infile, *outfile;        /* main input and output streams */
  216.     FILE *tmpfile;
  217.     unsigned high, lim, low;
  218.     BOOL more_text;
  219.  
  220.     puts(SIGNON);
  221.     linbuf = endext();        /* start of text buffer area */
  222.     maxtext = topofmem() - endext() - 500;
  223.     tmpfile = buffers[0];
  224.     options(&argc, argv);    /* process command line options */
  225.     if ( argc != 3 ) {
  226.       usage("");
  227.       }
  228.     infile = buffers[1];
  229.     if ( fopen(argv[1], infile) == ERROR ) {
  230.       puts("Can't open ");
  231.       puts(argv[1]);
  232.       exit(-1);
  233.       }
  234. #if VERBOSE
  235.     fputs("Beginning initial formation run\n", stderr);
  236. #endif
  237.     high = 0;        /* Initial formation of runs:    */
  238.     do {
  239.       more_text = gtext(infile);
  240.       quick(nlines);        
  241.       high++;
  242.       makfil(high, tmpfile);
  243.       ptext(tmpfile);
  244.       fclout(tmpfile);
  245.       } while ( more_text );
  246.     fclose(infile);        /* free up the input file buffer */
  247. #if VERBOSE
  248.     fputs("Beginning merge operation\n", stderr);
  249. #endif
  250.     for ( low = 1; low < high; low += MERGEORDER ) { /* merge */
  251.       lim = min(low + MERGEORDER - 1, high);
  252.       gopen(low, lim);        /* open files */
  253.       high++;
  254.       makfil(high, tmpfile);
  255.       merge(lim - low + 1, tmpfile);
  256.       fclout(tmpfile);    /* terminate, flush and close file */
  257.       gremov(low, lim);
  258.       }
  259.     /*
  260.      * Now write the sorted output file:
  261.      */
  262. #if VERBOSE
  263.     fputs("Merge c